package leetcode.D300.T207;

import java.util.ArrayList;
import java.util.List;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-17 12:20:12 星期四
 */

class Solution {

    private boolean hasCirle = false;
    private boolean[] visited;
    private boolean[] path;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        path = new boolean[numCourses];
        for (int i=0; i<numCourses; ++i) {
            tranverse(graph, i);
            if (hasCirle)
                return false;
        }
        return true;
    }

    private void tranverse(List<Integer>[] graph, int v) {
        if (path[v])
            hasCirle = true;
        if (hasCirle || visited[v])
            return;
        visited[v] = true;
        path[v] = true;
        for (int i=0; i<graph[v].size(); ++i) {
            tranverse(graph, graph[v].get(i));
        }
        path[v] = false;
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new List[numCourses];
        for (int i=0; i<numCourses; i++)
            graph[i] = new ArrayList<Integer>();
        for(int i=0; i<prerequisites.length; ++i) {
            int u = prerequisites[i][0], v = prerequisites[i][1];
            graph[v].add(u);
        }
        return graph;
    }
}